package com.c2b.algorithm.leetcode.base;

import java.util.ArrayDeque;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * <a href='https://leetcode.cn/problems/kth-largest-sum-in-a-binary-tree/'>二叉树中的第 K 大层和(Kth Largest Sum in a Binary Tree)</a>
 * <p>给你一棵二叉树的根节点 root 和一个正整数 k 。</p>
 * <p>树中的 层和 是指 同一层 上节点值的总和。</p>
 * <p>返回树中第 k 大的层和（不一定不同）。如果树少于 k 层，则返回 -1 。</p>
 * <p>注意，如果两个节点与根节点的距离相同，则认为它们在同一层。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [5,8,9,2,1,3,7,4,6], k = 2
 *      输出：13
 *      解释：树中每一层的层和分别是：
 *          - Level 1: 5
 *          - Level 2: 8 + 9 = 17
 *          - Level 3: 2 + 1 + 3 + 7 = 13
 *          - Level 4: 4 + 6 = 10
 *          第 2 大的层和等于 13 。
 *
 * 示例 2：
 *      输入：root = [1,2,null,3], k = 1
 *      输出：3
 *      解释：最大的层和是 3 。
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>树中的节点数为 n</li>
 *         <li>2 <= n <= 10^5</li>
 *         <li>1 <= Node.val <= 10^6</li>
 *         <li>1 <= k <= n</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/3/1 15:48
 */
public class LC2583KthLargestSumInBinaryTree_M {

    static class Solution {
        public long kthLargestLevelSum(TreeNode root, int k) {
            if (k <= 0) {
                return -1;
            }
            PriorityQueue<Long> priorityQueue = new PriorityQueue<>();
            Queue<TreeNode> queue = new ArrayDeque<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                int currLevelNodeSize = queue.size();
                long currLevelNodeValSum = 0;
                for (int i = 0; i < currLevelNodeSize; i++) {
                    TreeNode node = queue.poll();
                    currLevelNodeValSum += node.val;
                    if (node.left != null) {
                        queue.add(node.left);
                    }
                    if (node.right != null) {
                        queue.add(node.right);
                    }
                }
                if (priorityQueue.size() < k) {
                    priorityQueue.offer(currLevelNodeValSum);
                } else {
                    if (priorityQueue.peek() < currLevelNodeValSum) {
                        priorityQueue.poll();
                        priorityQueue.offer(currLevelNodeValSum);
                    }
                }
            }
            return priorityQueue.size() >= k ? priorityQueue.peek() : -1;
        }
    }
}
